The present invention is directed to communications networking. It is directed particularly to providing routing for private wide-area networks.
1. Private Wide-Area Networks
An enterprise that has many sites can build a private wide-area network by placing routers at each site and using leased lines to interconnect them. A router that has a wide-area connection to another router may be called a “backbone router.” The “backbone network” is the set of backbone routers and their interconnections.
If every backbone router is connected to every other backbone router, the backbone network is said to be “fully meshed.” In a fully meshed backbone network, data that travel from one site to another go through the backbone router at an origin site (“ingress router”), travel over the leased line to the backbone router at the target site (“egress router”), and then enter the target site. More commonly, though, the backbone network is not fully meshed; a router is connected to only a small number of others (three or four). In such a sparse topology, the ingress and egress routers may not be directly connected. In this case, data may have to pass through several additional, “transit” routers on the way from ingress to egress.
In a private network like this, the design and operation of the backbone network is the responsibility of the enterprise. A routing algorithm must run in the backbone routers, enabling them to tell each other the addresses of the destinations to which they can respectively afford access.
It is worth noting that a leased line is not actually a piece of wire going from one site to another. It is really a circuit through some circuit-switching network. But this is of no import to the enterprise network manager, to whom those circuits can be considered simple unstructured pipes. Conversely, although the telephone network itself requires considerable management, the telephone-network managers do not need to know anything about the enterprise backbone network; to them, the telephone network just provides point-to-point connections. They do not need to know what role these connections might be playing in an enterprise data network.
We may say that the enterprise network is “overlaid” on top of the telephone network. The enterprise network can be called the “higher layer” network, the telephone network the “lower layer” network. Both networks exist, but each is transparent to the other. The enterprise's backbone routers exchange routing information with each other, but the telephone switches do not store or process that routing information. That is, backbone routers are “routing peers” of each other, but they are not routing peers of the telephone switches. This way of building a higher-layer network on top of a lower-layer network is called the “overlay model.”
2. Virtual Private Networks
Wide-area enterprise networks are now more likely to be built on top of frame-relay and ATM networks than on top of circuit-switched (telephone) networks. Whereas a telephone network really provides circuits between backbone routers, a frame-relay or ATM network provides “virtual circuits” between backbone routers. But this changes nothing as far as the enterprise's routing task is concerned; the overlay model still applies even though the lower-layer network is now a frame-relay or ATM network rather than a circuit-switched one, i.e., even though virtual rather than fixed circuits make the point-to-point connections between backbone routers. The two networks are still transparent to each other. The enterprise network manager still has a wide-area backbone to design and operate. However, because the circuits are “virtual,” this is usually called a “virtual private network” (VPN) instead of a “private network.”
Since the two networks are transparent to each other in the overlay model, that model is distinguished by the fact that the enterprise's backbone routers do not share with the (service provider's) frame-relay or ATM switches the routing information that they must share with each other. This causes inefficiency when the enterprise's backbone routers are not fully meshed. In such networks, some packets go from the ingress router through one or more transit routers before they reach the egress router. At each one of these “hops,” the packet leaves the frame-relay or ATM network and then enters it again. This is sub-optimal—there is little value in having a packet go in and out of the frame-relay or ATM network multiple times.
This problem can be avoided by making the enterprise backbone fully meshed, but that causes problems of its own. The number of virtual circuits the enterprise has to pay the service provider for to make the network fully meshed grows as the square of the number of backbone routers. Apart from the cost, routing algorithms tend to scale poorly as the number of direct connections between routers grows. This causes additional problems.
The overlay model also tends to result in extra traffic when multicast is in use. It is usually impractical or undesirable for the “lower layer” network to do the necessary packet replication, so all packet replication must be done in the “higher layer” network, even if a number of replicated packets must then follow the same “lower layer” path up to a point.
3. The Peer Model
Since these considerations all impose upon the resources of an enterprise for which communications is not necessarily a core competence, a service provider (“SP”) can afford its customers greater value if it absorbs the task of designing and operating the backbone. More specifically, the SP should so organize and operate the backbone that, from the point of view of a particular site administrator, every enterprise network address not located at a given site is reachable through the SP's backbone network. How the SP's backbone decides to route the traffic is the SP's concern, not that of the customer enterprise. So the customer enterprise does not really need to maintain a backbone router at each site; it just needs a router that attaches to one of the SP's backbone routers. As will become apparent, providing such an organization involves abandoning the overlay model for a different model. The new model will be called the “peer model” for reasons that will be set forth below.
Terminology:                C-network: the enterprise network, consisting of C-routers, which are maintained and operated by the enterprise.        P-network: the SP network, consisting of P-routers, which the SP maintains and operates.        CE-router: an “edge router” in the C-network, i.e., a C-router that attaches directly to a P-router and is a routing peer of the P-router.        PE-router: an “edge router” in the P-network, i.e., a P-router that attaches directly to a C-router and is a routing peer of the C-router.        
If a P-router is not a PE-router, i.e., not an edge router, it is a transit router. The concept of edge and transit routers is relative to specific VPNs. If a given one of the SP's routers receives a given VPN's traffic from and forwards it to only others of the SP's routers, the given router is a transit router vis-à-vis the given VPN. Yet that same router may receive another VPN's traffic from and/or forward it to one of that other VPN's edge routers, in which case the given SP router is an edge router from the other VPN's point of view.
In the conventional peer model, where “virtual routers” (i.e., one instance of the routing algorithm per VPN) are used, all C-routers within the same VPN are routing peers of each other. But two C-routers will be routing adjacencies of each other only if they are at the same site. Each site has at least one CE router, each of which is directly attached to at least one PE router, which is its routing peer. Since CE routers do not exchange routing information with each other, there is no virtual backbone for the enterprise to manage, and there is never any need for data to travel through transit CE routers. Data go from the ingress CE router through a sequence of P-routers to the egress CE router. So the resultant routing is optimal. These clear customer benefits have led certain SPs to adopt the peer model.
The conventional peer-model approach also enables the SP to solve certain problems that arise from using a common backbone network for more than one client. One of these is address duplication. Although there is an international assigned-number authority from which unique addresses can be obtained, many enterprise networks simply assign their private-network addresses themselves. So their addresses are unique only within the particular enterprise: they may duplicate addresses that another customer enterprise uses. An SP trying to use, say, an Internet-Protocol (“IP”) backbone as the backbone for different enterprise networks having overlapping address spaces needs to provide its P-routers with a way of identifying and selecting a route to the one of potentially many same-address destinations to which it should forward a packet.
So the SP makes use of a “virtual router.” When a PE router receives a packet received from a CE router, the PE router “tags” the packet with an indication of the C-network where it originated. It then bases its determination of what router to forward the packet to not only on the packet's destination address but also on the identity of the originating C-network. At each subsequent hop, the router looks up the packet's destination address in the forwarding table specific to the C-network that the tag designates.
This also solves another multiple-customer problem, that of the access control. If an enterprise buys network-backbone service from an Internet SP, it wants some assurance that its network receives only packets that originated in its own network. It also wants to be sure that packets originating in its network do not leave the enterprise network by accident. Of course, two enterprises might want to be able to communicate directly, or to communicate over the Internet. But they want such communication to occur only through “firewalls.” By using the virtual router, the SP solves this problem, too.